#include "quickSelect.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "quickSort.h"
#include "insertSort.h"
void QSelect(ElementType A[], int k, int left, int right)
{
    int i, j;
    ElementType mid;
    if (left + Cutoff <= right)
    {
        mid = Median3(A, left, right);
        i = left;
        j = right - 1;
        for (;;)
        {
            while (A[++i] < mid)
            {
            };
            while (A[--j] > mid)
            {
            };
            if (i < j)
            {
                Swap(&A[i], &A[j]);
            }
            else
            {
                break;
            }
        }
        //将中值还原
        Swap(&A[i], &A[right - 1]);
        if (i >= k)
        {
            //选取的中值在k右侧，即k在左侧
            QSelect(A, k, left, i - 1);
        }
        else
        {
            QSelect(A, k, i + 1, right);
        }
    }
    else
    {
        InsertionSort(A + left, right - left + 1);
    }
}

ElementType QuickSelect(ElementType A[], int k, int N)
{
    ElementType tmp;
    ElementType *tmpArray;
    tmpArray = malloc(N * sizeof(ElementType));
    if (tmpArray != NULL)
    {
        memcpy(tmpArray, A, N * sizeof(ElementType));
        QSelect(tmpArray, k - 1, 0, N - 1);
        tmp = tmpArray[k - 1];
        free(tmpArray);
    }
    else
    {
        printf("malloc error\n");
        exit(EXIT_SUCCESS);
    }
    return tmp;
}